package algorithms.question.class19;

import common.util.MyUtil;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/
 *
 * @author guichang
 * @date 2021/8/19
 */

@SuppressWarnings("all")
public class Code4_最小区间 {
    // 有序表，每个列表取一个值放进去

    public static void main(String[] args) {
//        List<Integer> l1 = Arrays.asList(4, 10, 15, 24, 26);
//        List<Integer> l2 = Arrays.asList(0, 9, 12, 20);
//        List<Integer> l3 = Arrays.asList(5, 18, 22, 30);
//        List<List<Integer>> nums = Arrays.asList(l1, l2, l3);
//        MyUtil.print(Arrays.toString(smallestRange(nums))); // [20,24]

        List<Integer> l1 = Arrays.asList(1, 2, 3);
        List<Integer> l2 = Arrays.asList(1, 2, 3);
        List<Integer> l3 = Arrays.asList(1, 2, 3);
        List<List<Integer>> nums = Arrays.asList(l1, l2, l3);
        MyUtil.print(Arrays.toString(smallestRange(nums))); // [1,1]
    }

    public static int[] smallestRange(List<List<Integer>> nums) {
        if (nums == null || nums.size() == 0) {
            return null;
        }
        // 按value由小到大
        PriorityQueue<Info> queue = new PriorityQueue<>(nums.size(), (a, b) -> a.value - b.value);
        // help 主要是取最大值
        PriorityQueue<Info> help = new PriorityQueue<>(nums.size(), (a, b) -> b.value - a.value);
        // 每个数先放第一个数进去
        for (int i = 0; i < nums.size(); i++) {
            queue.offer(new Info(nums.get(i).get(0), i, 0));
            help.offer(new Info(nums.get(i).get(0), i, 0));
        }
        int[] res = new int[2];
        res[1] = Integer.MAX_VALUE;
        while (true) {
            // 比较上一个
            Info first = queue.poll();
            Info last = help.peek();
            help.remove(first);
            if (last.value - first.value < res[1] - res[0]) {
                res[0] = first.value;
                res[1] = last.value;
            }
            List<Integer> fromList = nums.get(first.from);
            // 到最后一个了，跳出循环
            if (first.index == fromList.size() - 1) {
                break;
            }
            // 后面还有元素，加进来
            queue.offer(new Info(fromList.get(first.index + 1), first.from, first.index + 1));
            help.offer(new Info(fromList.get(first.index + 1), first.from, first.index + 1));
        }
        return res;
    }

    /**
     * 存放值和所在的list
     */
    private static class Info {
        int value;
        int from;
        int index;

        public Info(int value, int from, int index) {
            this.value = value;
            this.from = from;
            this.index = index;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Info)) {
                return false;
            }
            Info info = (Info) obj;

            return info.value == value && info.from == from && info.index == index;
        }
    }

}